package problem879;

//879.盈利计划
//https://leetcode.cn/problems/profitable-schemes/

// class Solution {
//     public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
//         int len = group.length;
//         int mod = 1000_000_007;
//         int[][][] dp = new int[len+1][n+1][minProfit+1];
//         for(int j = 0; j<=n; j++) {
//             dp[0][j][0] = 1;
//         }
//         for(int i = 1; i<=len; i++) {
//             for(int j = 0; j<=n; j++) {
//                 for(int k = 0; k<=minProfit; k++) {
//                     dp[i][j][k] = dp[i-1][j][k];
//                     if(j-group[i-1] >= 0) dp[i][j][k] += dp[i-1][j-group[i-1]][Math.max(0, k-profit[i-1])];
//                     dp[i][j][k] %= mod;
//                 }
//             }
//         }
//         return dp[len][n][minProfit];
//     }
// }

/*
dp[i][j][k]:从前i个计划中选, 总人数不超过j, 产生k利润的选法

*/

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length;
        int mod = 1000_000_007;
        int[][] dp = new int[n+1][minProfit+1];
        for(int j = 0; j<=n; j++) {
            dp[j][0] = 1;
        }
        for(int i = 1; i<=len; i++) {
            for(int j = n; j>=group[i-1]; j--) {
                for(int k = 0; k<=minProfit; k++) {
                    dp[j][k] += dp[j-group[i-1]][Math.max(0, k-profit[i-1])];
                    dp[j][k] %= mod;
                }
            }
        }
        return dp[n][minProfit];
    }
}

/*
dp[i][j][k]:从前i个计划中选, 总人数不超过j, 产生k利润的选法

*/